home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / prgtools / gnustuff / tos / futils / futils~1 / src / misc1s.zoo / misc1 / combine / pass1.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-06-23  |  12.1 KB  |  537 lines

  1. #include <stdio.h>
  2. #include <ctype.h>
  3. #include "util.h"
  4. #include "combine.h"
  5. /*
  6.  * pass1: Perform the file read and table build pass
  7.  *
  8.  * This routine reads all of the records of all of the input files
  9.  * into the cache, symbol table, and record array.
  10.  *
  11.  * This routine alternately reads one record from each file. Assuming
  12.  * that the files have similar contents, this technique improves the
  13.  * chance that a record from the second and third files will be in
  14.  * the cache.
  15.  *
  16.  * Return value:
  17.  *    This procedure has no return value.
  18.  */
  19.  
  20. void pass1 () {
  21.  
  22.     int    i;        /* Misc. variable */
  23.  
  24.     int    index;        /* Index into record array */
  25.  
  26.     int    files_left;    /* number of files left to do */
  27.  
  28.     bool file_done[MAX_FILE_COUNT];/* TRUE if EOT reached on file */
  29.  
  30.     int    status;        /* Misc. status variable */
  31.  
  32.  
  33.  
  34.        /*
  35.     * Initialize completion parameters.
  36.     */
  37.  
  38.     files_left = file_count;
  39.     for (i = 0; i < file_count; ++i) {
  40.         file_done[i] = FALSE;
  41.     }
  42.  
  43.  
  44.     /*
  45.      * For each iteration of the file read the nth record of the each file.
  46.      */
  47.  
  48.     for (index = BEGIN_INDEX + 1; files_left != 0; ++index) {
  49.  
  50.         /*
  51.          * Handle each file.
  52.          */
  53.  
  54.         for (i = 0; i < file_count; ++i) {
  55.  
  56.             if (!file_done[i]) {
  57.  
  58.                 if (index + 1 >= files[i].record_array_alloc) {
  59.                     files[i].record_array_alloc += RA_INCR;
  60.                     files[i].record = (record_type *)
  61.                         realloc(files[i].record,
  62.                         files[i].record_array_alloc * sizeof (record_type));
  63.                     if ( files[i].record == 0 ){
  64.                         error( "out of memory -- files are way too big");
  65.                     }
  66.                 }
  67.  
  68.                 status = pass1_read_record (&files[i], index);
  69.  
  70.                 if (status < 0) {
  71.                     file_done[i] = TRUE;
  72.                     files[i].record_array_size = index + 1;
  73.                     --files_left;
  74.                     if (files_left == 0) {
  75.                         break;
  76.                     }
  77.                 }
  78.  
  79.             }
  80.  
  81.         }
  82.  
  83.     }
  84.  
  85. }
  86. /*
  87.  * pass1_read_record: read a record for pass 1
  88.  *
  89.  * This routine reads a record into the cache, symbol table, and record
  90.  * array.
  91.  * For each record read, a unique hash value is computed.
  92.  * That hash value is an index into the symbol table.
  93.  *
  94.  * Return value:
  95.  *     0:   record read as requested.
  96.  *    -1:   end of the file was reached.
  97.  */
  98.  
  99. int    pass1_read_record (file_ptr, index)
  100.     file_type * file_ptr;    /* input -- Description of the file
  101.                    to read record from. */
  102.  
  103.     int    index;        /* input -- Record number of the record
  104.                    currently being read. */
  105.  
  106. {
  107.  
  108.     static    cache_entry_type * cache_ptr = 0;
  109.                 /* Pointer to the cache entry which is used to read into. This cache buffer is linked onto the cache list if this is the first time the record is read. */
  110.  
  111.     register int   *end_int_ptr;
  112.                 /* Pointer to last integer in hashing algorithm */
  113.  
  114.     cache_entry_type * found_cache_ptr;
  115.                 /* Pointer to the cache entry found by hashing */
  116.  
  117.     register int   *found_int_ptr;/* co-erced pointer to found record */
  118.  
  119.     int    hash_code;    /* index into symbol table */
  120.  
  121.     int    i;        /* Misc. variable */
  122.  
  123.     register int   *int_ptr;/* Co-erced pointer to read record */
  124.  
  125.     char    mbuffer[LINE_LENGTH];/* Misc. buffer */
  126.  
  127.     int    probe_count;    /* Number a rehashes attempted. */
  128.  
  129.     int    quotient;    /* quotient of sum/table size.
  130.                    This value is used as the increment when
  131.                    re-hashing into the symbol table */
  132.  
  133.     cache_entry_type * reread_cache_ptr;
  134.                 /* Pointer to the cache buffer used for cache
  135.                    re-read operation. */
  136.  
  137.     file_type * reread_file_ptr;
  138.                 /* Pointer to the file to read from on a
  139.                    cache re-read operation. */
  140.  
  141.     int    reread_index;    /* Record number to read on a cache re-read operation. */
  142.  
  143.     rfa_type rfa;        /* RFA of record read */
  144.  
  145.     int    status;        /* Misc. status variable */
  146.  
  147.     register int    sum;    /* Sum of all bytes in a record */
  148.  
  149.  
  150.     /*
  151.      * If we don't have a cache buffer laying around,
  152.      *    delink one from end of list.
  153.      */
  154.  
  155.     if (cache_ptr == 0) {
  156.         deq_tail_dll (cache_head_ptr, cache_tail_ptr, cache_ptr,
  157.                 cache_next_ptr, cache_prev_ptr);
  158.         if (cache_ptr -> hash_code != HASH_FREE_ENTRY) {
  159.             sym_tab_cache_ptr[cache_ptr -> hash_code] =
  160.                 (cache_entry_type *) CACHE_NOT_IN_CACHE;
  161.         }
  162.     }
  163.  
  164.     /*
  165.      * Read the next record into our local cache entry.
  166.      */
  167.  
  168.     rfa = ftell(file_ptr->seq_fd);
  169.     if (p1_debug) {
  170.         printf ("index: %d hash_col: %d cache_miss: %d",
  171.                 index, hash_collisions, cache_miss);
  172.     }
  173.  
  174.     status = read_into_cache( file_ptr -> seq_fd, rfa, cache_ptr );
  175.     if (status < 0) {
  176.         return (-1);
  177.     }
  178.  
  179.     /*
  180.      * Pad to end of word with blanks, this allows hashing and comparison
  181.      * algorithms to be word oriented rather than byte oriented.
  182.      *
  183.      * Compress the record based on input parameters.
  184.      */
  185.  
  186.     if (cache_ptr -> record_length >= 0) {
  187.  
  188.         if (compress_records) {
  189.             pass1_record_compress (cache_ptr -> recordp,
  190.                     &cache_ptr -> record_length);
  191.         }
  192.  
  193.         /* Pad to the end of the word with blanks */
  194.         for (i = 0; i < sizeof (int) - 1; ++i) {
  195.             cache_ptr->recordp[cache_ptr->record_length + i] = ' ';
  196.         }
  197.     }
  198.  
  199.     /*
  200.      * Compute hash code for the record.
  201.      *
  202.      * The value is shifted on each iteration to ensure that the
  203.      * magnitude of the sum is large enough. Otherwise when the sum is
  204.      * divided by the size of the symbol table, the remainder will be
  205.      * clustered toward the beginning of the table.
  206.      */
  207.  
  208.     sum = 0;
  209.     int_ptr = (int *) cache_ptr -> recordp;
  210.     end_int_ptr = int_ptr +
  211.         ((cache_ptr->record_length + sizeof (int) - 1) / sizeof (int));
  212.     for (; int_ptr < end_int_ptr; int_ptr++) {
  213.  
  214.     /*    if (p1_debug) {
  215.             printf ("sum: %x ", sum);
  216.         }*/
  217.     /*
  218.      * The next statement does a left rotate of 7. The add operation is
  219.      * used instead of a logical-or operation since the right shift
  220.      * is an arithmetic shift which propogates the sign bit. An
  221.      * or operation into 25 bits of propogated sign bit loses a lot
  222.      * of significance.
  223.      */
  224.         sum = (sum >> (sizeof (int) * 8 - 7)) + (sum << 7);/* left rotate 7 */
  225.     /*    if (p1_debug) {
  226.             printf ("sum<<7: %x ", sum);
  227.         } */
  228.         sum += *int_ptr;
  229.     /*    if (p1_debug) {
  230.             printf ("sum:%x value:%X\n", sum, *int_ptr);
  231.         } */
  232.     }
  233.     sum = abs (sum);
  234.     if (p1_debug) {
  235.         printf ("sum: %d ", sum);
  236.     }
  237.  
  238.     hash_code = sum % sym_tab_size;
  239.     quotient = sum / sym_tab_size;
  240.     if ((quotient % sym_tab_size) == 0) {
  241.         quotient = 1;
  242.     }
  243.  
  244.     /*
  245.      * Loop until a unique hash code is found.
  246.      */
  247.  
  248.     for (probe_count = 0; probe_count < sym_tab_size;
  249.             ++probe_count, ++hash_collisions) {
  250.         do {
  251.             hash_code = (hash_code + quotient) % sym_tab_size;
  252.         } while (hash_code == 0);/* ensure sym tab loc 0 is never used */
  253.  
  254.         /*
  255.          * if symbol table entry is used but record is not is cache,
  256.          *     read record into cache by flushing the least recently
  257.          *    entry entry from the cache.
  258.          */
  259.  
  260.         if (p1_debug) {
  261.             printf ("hash_code: %d\n", hash_code);
  262.         }
  263.  
  264.         if ((int) sym_tab_cache_ptr[hash_code] == CACHE_NOT_IN_CACHE) {
  265.  
  266.             cache_miss++;
  267.             if (p1_debug) {
  268.                 printf ("cache_miss\n");
  269.             }
  270.  
  271.             deq_tail_dll (cache_head_ptr, cache_tail_ptr, reread_cache_ptr,
  272.                     cache_next_ptr, cache_prev_ptr);
  273.  
  274.             if (reread_cache_ptr -> hash_code != HASH_FREE_ENTRY) {
  275.                 sym_tab_cache_ptr[reread_cache_ptr -> hash_code] =
  276.                     (cache_entry_type *) CACHE_NOT_IN_CACHE;
  277.             }
  278.  
  279.             for (i = 0; i < file_count; ++i) {
  280.                 if (files[i].sym_tab_index[hash_code] != 0) {
  281.                     reread_file_ptr = &files[i];
  282.                     break;
  283.                 }
  284.             }
  285.  
  286.             if (i == file_count) {
  287.                 error ("Consistency error on rehash read");
  288.             }
  289.  
  290.             reread_index = abs (reread_file_ptr -> sym_tab_index[hash_code]);
  291.  
  292.             reread_into_cache( reread_file_ptr, reread_index,
  293.                 reread_cache_ptr);
  294.  
  295.             if (reread_cache_ptr -> record_length >= 0) {
  296.  
  297.                 if (compress_records) {
  298.                     pass1_record_compress (
  299.                         reread_cache_ptr -> recordp,
  300.                         &reread_cache_ptr -> record_length);
  301.                 }
  302.  
  303.                 for (i = 0; i < sizeof (int) - 1; ++i) {
  304.                     reread_cache_ptr->
  305.                     recordp[reread_cache_ptr->record_length + i] = ' ';
  306.                 }
  307.             }
  308.  
  309.             if (p1_debug) {
  310.                 printf ("%d %s\n",
  311.                     reread_cache_ptr -> record_length,
  312.                     reread_cache_ptr -> recordp);
  313.             }
  314.  
  315.             sym_tab_cache_ptr[hash_code] = reread_cache_ptr;
  316.             reread_cache_ptr -> hash_code = hash_code;
  317.             enq_head_dll (cache_head_ptr, cache_tail_ptr,
  318.                     reread_cache_ptr,
  319.                     cache_next_ptr, cache_prev_ptr);
  320.         }
  321.  
  322.         /*
  323.          * if this is the first time this hash code has been used,
  324.          *     point the symbol table to the cache entry,
  325.          *     insert the cache entry in the front of the cache.
  326.          *     break out of loop.
  327.          */
  328.  
  329.         if (sym_tab_cache_ptr[hash_code] == CACHE_FREE_ENTRY) {
  330.             if (p1_debug) {
  331.                 printf ("cache_free_entry\n");
  332.             }
  333.             sym_tab_cache_ptr[hash_code] = cache_ptr;
  334.             cache_ptr -> hash_code = hash_code;
  335.             enq_head_dll (cache_head_ptr, cache_tail_ptr, cache_ptr,
  336.                     cache_next_ptr, cache_prev_ptr);
  337.             cache_ptr = 0;
  338.             break;
  339.  
  340.         /*
  341.          * if this hash code is used and the record is in cache,
  342.          *     Compare our record with the one in the cache.
  343.          *     if the records are the same,
  344.          *      move cache entry to front of list,
  345.          *      break out of the loop.
  346.          */
  347.  
  348.         } else {
  349.             found_cache_ptr = sym_tab_cache_ptr[hash_code];
  350.             if (p1_debug) {
  351.                 printf ("len1: %d len2: %d\n",
  352.                     cache_ptr -> record_length,
  353.                     found_cache_ptr -> record_length);
  354.             }
  355.             if (cache_ptr->record_length ==
  356.                 found_cache_ptr->record_length) {
  357.  
  358.                 found_int_ptr = (int *) found_cache_ptr->recordp;
  359.                 int_ptr = (int *) cache_ptr -> recordp;
  360.                 end_int_ptr = int_ptr +
  361.                     ((cache_ptr -> record_length +
  362.                     sizeof (int) - 1) / sizeof (int));
  363.                 for (; int_ptr < end_int_ptr; int_ptr++) {
  364.                 /* printf( "v1: %x v2:%x\n", *int_ptr, *found_int_ptr ) ; */
  365.                     if (*int_ptr != *found_int_ptr) {
  366.                         break;
  367.                     }
  368.                     found_int_ptr++;
  369.                 }
  370.  
  371.                 if (int_ptr >= end_int_ptr) {
  372.                     rem_dll (cache_head_ptr,
  373.                          cache_tail_ptr,
  374.                          found_cache_ptr,
  375.                          cache_next_ptr,
  376.                          cache_prev_ptr);
  377.                     enq_head_dll (cache_head_ptr,
  378.                               cache_tail_ptr,
  379.                               found_cache_ptr,
  380.                               cache_next_ptr,
  381.                               cache_prev_ptr);
  382.                     break;
  383.                 }
  384.  
  385.             }
  386.         }
  387.  
  388.     }
  389.  
  390.     if (probe_count == sym_tab_size) {
  391.         error ("Symbol table overflow");
  392.     }
  393.  
  394.     /*
  395.      * If the record array for the file has overflowed,
  396.      *     fatal error.
  397.      */
  398.  
  399.     if (index + 1 >= file_ptr -> record_array_alloc) {
  400.         error ("record array size computed wrong");
  401.     }
  402.  
  403.      /*
  404.       * Install record into record array.
  405.       */
  406.  
  407.     file_ptr -> record[index].rfa = rfa;
  408.     file_ptr -> record[index].value[0] = -hash_code;
  409.     file_ptr -> record[index].value[1] = -hash_code;
  410.  
  411.     /*
  412.      * Install line into symbol table.
  413.      */
  414.  
  415.     if (file_ptr -> sym_tab_index[hash_code] == 0) {
  416.         file_ptr -> sym_tab_index[hash_code] = index;
  417.     }
  418.     else {
  419.         file_ptr -> sym_tab_index[hash_code] = -index;
  420.     }
  421.  
  422.     return (0);
  423.  
  424. }
  425. /*
  426.  * pass1_record_compress: compress out insignificant bytes in a record.
  427.  *
  428.  * This routine handles options which compares only a portion of the
  429.  * record. For the -b option, all occurrences of multiple blanks are
  430.  * compressed into a single blank. For the -c option, all columns not
  431.  * specified are removed.
  432.  *
  433.  * Return value:
  434.  *    This procedure has no return value.
  435.  */
  436.  
  437. void pass1_record_compress (record_ptr, record_len_ptr)
  438.     char   *record_ptr;    /* input/output */
  439.                 /* Record to be compressed in place. */
  440.  
  441.     int    *record_len_ptr; /* input/output */
  442.                 /* Length of record. */
  443.  
  444. {
  445.  
  446.     int    i;        /* Misc. variable */
  447.  
  448.     int    j;        /* Misc. variable */
  449.  
  450.     int    k;        /* Misc. variable */
  451.  
  452.     bool space;        /* TRUE if currently doing a space or tab sequence */
  453.  
  454.  
  455.     /*
  456.      * Handle column ranges:
  457.      */
  458.     if (column_count != 0) {
  459.         k = 0;
  460.         for (i = 0; i < column_count; ++i) {
  461.  
  462.             for (j = first_column[i];
  463.                 j <= last_column[i] && j < *record_len_ptr;
  464.                 ++j) {
  465.  
  466.                 record_ptr[k] = record_ptr[j];
  467.                 ++k;
  468.             }
  469.  
  470.         }
  471.  
  472.         *record_len_ptr = k;
  473.  
  474.     }
  475.  
  476.     /*
  477.      * Handle blank compression:
  478.      *
  479.      * Blank compression converts all groups of blanks and horizontal
  480.      * tabs to a single blank.
  481.      */
  482.  
  483.     if (blank_compress) {
  484.         k = 0;
  485.         space = FALSE;
  486.  
  487.         for (i = 0; i < *record_len_ptr; ++i) {
  488.  
  489.             if (record_ptr[i] == ' ' || record_ptr[i] == '\t') {
  490.                 space = TRUE;
  491.             } else {
  492.                 if (space) {
  493.                     record_ptr[k++] = ' ';
  494.                     space = FALSE;
  495.                 }
  496.                 record_ptr[k++] = record_ptr[i];
  497.             }
  498.  
  499.         }
  500.  
  501.         if (space) {
  502.             record_ptr[k++] = ' ';
  503.         }
  504.  
  505.         *record_len_ptr = k;
  506.  
  507.     }
  508.  
  509.     /*
  510.      * Handle blank removal:
  511.      *
  512.      * Blank removal removes all blanks and horizontal tabs.
  513.      */
  514.  
  515.     if (blank_remove) {
  516.         k = 0;
  517.         space = FALSE;
  518.  
  519.         for (i = 0; i < *record_len_ptr; ++i) {
  520.  
  521.             if (record_ptr[i] == ' ' || record_ptr[i] == '\t') {
  522.                 space = TRUE;
  523.             } else {
  524.                 if (space) {
  525.                     space = FALSE;
  526.                 }
  527.                 record_ptr[k++] = record_ptr[i];
  528.             }
  529.  
  530.         }
  531.  
  532.         *record_len_ptr = k;
  533.  
  534.     }
  535.  
  536. }
  537.